package com.leetcode.partition2;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/19 9:00
 */
public class LC113路径总和2 {

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) return answer;
        List<Integer> path = new ArrayList<>();
        path.add(root.val);
        backtracking(root, targetSum, answer, path, root.val);
        return answer;
    }

    public static void main(String[] args) {
        TreeNode r1 = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1))));
        System.out.println(pathSum(r1, 22));
    }

    private static void backtracking(TreeNode root, final int targetSum, List<List<Integer>> answer, List<Integer> path, int sum) {
        if (root.left == null && root.right == null) {
            if (sum == targetSum) answer.add(new ArrayList<>(path));
            return;
        }
        if (root.left != null) {
            path.add(root.left.val);
            backtracking(root.left, targetSum, answer, path, sum + root.left.val);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            backtracking(root.right, targetSum, answer, path, sum + root.right.val);
            path.remove(path.size() - 1);
        }
    }
}
